package recursion;

/** 八皇后问题 */
public class Queen8 {

  int max = 8;
  int[] arr = new int[max];

  public static void main(String[] args) {

    Queen8 queen=new Queen8();
    queen.queen8(0);
  }


  //依次摆放皇后
  public  void queen8(int n){
    if (n==max){//n==8，则第8个皇后已经放好
      print();
      return;
    }
    for (int i = 0; i < max; i++) {
      arr[n]=i;
      if (detect(n)){
        queen8(n+1);
      }
    }
  }

  // 放置第n个皇后，检测该皇后与前面已经放置的是否冲突
  public boolean detect(int n) {
    for (int i = 0; i < n; i++) {
      if (arr[n] == arr[i] || n - i == Math.abs(arr[n] - arr[i])) { // 是否在同一列，或者在一条斜线上
        return false;
      }
    }
    return true;
  }

  public void print() {
    for (int i : arr) {
      System.out.print(i + "  ");
    }
    System.out.println();
  }
}
